|
|
The combinatorics of pattern-avoiding matrices
Mikšaník, David ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Permutační matice P částečné vynechává kvazi-permutační matici A (jinými slovy, 01- matici takovou, že každý sloupec a řádek matice A obsahuje nejvýše jednu nenulovou hod- notu), pokud neexistuje podmatice P′ matice P stejné velikosti jako A splňující Ai,j ≤ P′ i,j pro každé indexy i a j. Kvazi-permutační matice A a B jsou částečně Wilf-ekvivalentní, pokud pro každé n ∈ N počet permutačních matic řádu n částečné vynechávajících A je stejný jako počet permutačních matic řádu n částečně vynechávajících B. Tyto pojmy zobecňují známý koncept vynechávání permutací a Wilfovy ekvivalence permutací. Stě- žejní oblast výzkumu je klasifikace permutací řádu k do tříd Wilfovy ekvivalence. Tato klasifikace je známa pro k = 1, 2, . . . , 7. V naší práci studujeme stejný problém pro kvazi- permutační matice. Konkrétně, klasifikujeme všech 371 kvazi-permutačních matic veli- kosti nejvýše 4×4 do říd částečné Wilfovy ekvivalence (dvě kvazi-permutační matice patří do stejné třídy právě tehdy, když jsou částečně Wilf-ekvivalentní). V průběhu odvodíme několik obecných výsledků o tom, jak zkonstruovat z jedné či dvou kvazi-permutačních matic více kvazi-permutačních matic, které jsou po dvou částečně Wilf-ekvivalentní. 1
|
host ::
RSS.